package com.yxp.offer;

import com.yxp.util.ListRandomNode;

/**
 * @Auther : yxpweb
 * @Date : 2021/8/14 10:03
 * @Description: 剑指 Offer 35. 复杂链表的复制
 */
public class Problem35 {

    public static void main(String[] args) {
        Problem35 problem35 = new Problem35();
        ListRandomNode node = new ListRandomNode(1);
        problem35.copyRandomList(node);
    }

    public ListRandomNode copyRandomList(ListRandomNode head) {
        if (head == null) {
            return null;
        }
        ListRandomNode curNode = head;
        // 复制当前指针指导的对象到 next
        while (curNode != null) {
            ListRandomNode newNode = new ListRandomNode(curNode.val);
            newNode.next = curNode.next;
            curNode.next = newNode;
            curNode = newNode.next;
        }
        curNode = head;
        // 复制random
        while (curNode != null) {
            ListRandomNode random = curNode.random;
            if (random != null) {
                curNode.next.random = random.next;
            }
            curNode = curNode.next.next;
        }
        ListRandomNode newHead = head.next;
        curNode = head;
        ListRandomNode tempNode;
        while (curNode.next != null) {
            tempNode = curNode.next;
            curNode.next = curNode.next.next;
            curNode = tempNode;
        }
        // 分离节点
        return newHead;
    }
}


